{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest String With A Given Numeric Value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getSmallestString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #具有给定数值的最小字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>小写字符 </strong>的 <strong>数值</strong> 是它在字母表中的位置（从 <code>1</code> 开始），因此 <code>a</code> 的数值为 <code>1</code> ，<code>b</code> 的数值为 <code>2</code> ，<code>c</code> 的数值为 <code>3</code> ，以此类推。</p>\n",
    "\n",
    "<p>字符串由若干小写字符组成，<strong>字符串的数值</strong> 为各字符的数值之和。例如，字符串 <code>\"abe\"</code> 的数值等于 <code>1 + 2 + 5 = 8</code> 。</p>\n",
    "\n",
    "<p>给你两个整数 <code>n</code> 和 <code>k</code> 。返回 <strong>长度</strong> 等于 <code>n</code> 且 <strong>数值</strong> 等于 <code>k</code> 的 <strong>字典序最小</strong> 的字符串。</p>\n",
    "\n",
    "<p>注意，如果字符串 <code>x</code> 在字典排序中位于 <code>y</code> 之前，就认为 <code>x</code> 字典序比 <code>y</code> 小，有以下两种情况：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>x</code> 是 <code>y</code> 的一个前缀；</li>\n",
    "\t<li>如果 <code>i</code> 是 <code>x[i] != y[i]</code> 的第一个位置，且 <code>x[i]</code> 在字母表中的位置比 <code>y[i]</code> 靠前。</li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, k = 27\n",
    "<strong>输出：</strong>\"aay\"\n",
    "<strong>解释：</strong>字符串的数值为 1 + 1 + 25 = 27，它是数值满足要求且长度等于 3 字典序最小的字符串。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, k = 73\n",
    "<strong>输出：</strong>\"aaszz\"\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= n <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>n <= k <= 26 * n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-string-with-a-given-numeric-value](https://leetcode.cn/problems/smallest-string-with-a-given-numeric-value/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-string-with-a-given-numeric-value](https://leetcode.cn/problems/smallest-string-with-a-given-numeric-value/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n27', '5\\n73']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        a,b = (k-n)%25,(k-n)//25\n",
    "        return ('a'*(n-b-1)+chr(ord('a')+a)+'z'*b)[-n:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        a,b = (k-n)%25,(k-n)//25\n",
    "        print(a,b)\n",
    "        return ('a'*(n-b-1)+chr(ord('a')+a)+'z'*b)[-n:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        # 从后往前添加字符即可\n",
    "        cur_index = n\n",
    "        s = \"\"\n",
    "        while True:\n",
    "            if k - (cur_index-1) > 26:\n",
    "                s = \"z\" + s\n",
    "                k = k - 26\n",
    "                cur_index -= 1\n",
    "            else:\n",
    "                s = chr(96 + (k - (cur_index - 1))) + s\n",
    "                cur_index -= 1\n",
    "                break\n",
    "        if cur_index > 0:\n",
    "            for i in range(cur_index):\n",
    "                s = \"a\" + s\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        k-=n\n",
    "        n2=k//25\n",
    "        m=k%25\n",
    "        if m==0:\n",
    "            n1=n-n2\n",
    "            return 'a'*n1 + 'z'*n2\n",
    "        else:\n",
    "            n1=n-1-n2\n",
    "            return 'a'*n1 + chr(ord('a')+m) + 'z'*n2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        y = lambda z: (k - z + 1 - n) / 25\n",
    "\n",
    "        for z in range(1, 27):\n",
    "            if y(z) == int(y(z)) and n - 1 - y(z) >= 0: \n",
    "                return int(n - 1 - y(z)) * \"a\" + chr(96 + z) + int(y(z)) * \"z\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        if(n == 0):\n",
    "            return ''\n",
    "        result = ''\n",
    "        mapping = {}\n",
    "        for i in range(1,26):\n",
    "            t = (26*n-k)//(26-i)\n",
    "            result += chr(ord('a')+i-1) * t\n",
    "            n -= t \n",
    "            k -= t*i\n",
    "        result += n*'z'\n",
    "        return result \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        a = (26 * n - k) // 25\n",
    "        left = k - a\n",
    "        z = left // 26\n",
    "        return 'a' * a + (chr(left % 26 + ord('a') - 1) if left % 26 else '') + z * 'z'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        if(n == 0):\n",
    "            return ''\n",
    "        result = ''\n",
    "        mapping = {}\n",
    "        for i in range(1,26):\n",
    "            t = (26*n-k)//(26-i)\n",
    "            result += chr(ord('a')+i-1) * t\n",
    "            n -= t \n",
    "            k -= t*i\n",
    "        result += n*'z'\n",
    "        return result \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        t = k - n\n",
    "        num_z, rest = divmod(t, 25)\n",
    "        num_a = n - num_z\n",
    "        special = ''\n",
    "        if rest:\n",
    "            num_a -= 1\n",
    "            special = chr(97 + rest)\n",
    "        return num_a * 'a' + special + num_z * 'z'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        z = (k - n) // 25   # 后缀z的个数\n",
    "        a = n - z - 1       # 前缀a的个数\n",
    "        s = (k - n) % 25    # 剩余数值\n",
    "        return ('' if z == n else 'a' * a + chr(s + 97)) + 'z' * z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        if k==26*n: return 'z' * n\n",
    "        nz = (k - n) // 25\n",
    "        na, mx = n - nz - 1, k - nz * 25 - n + 1\n",
    "        return 'a' * na + chr(ord('a')+mx-1) + 'z'*nz\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        ans = ''\n",
    "        while k > 0:\n",
    "            if k - 26 >= n - 1:\n",
    "                ans = 'z' + ans\n",
    "                k -= 26\n",
    "                n -= 1\n",
    "            elif k == n:\n",
    "                ans = 'a' * k + ans\n",
    "                k -= k\n",
    "                n -= n\n",
    "            else:    \n",
    "                ans = chr(ord('a') + k - n) + ans\n",
    "                k -= k - n + 1\n",
    "                n -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        if(n == 0):\n",
    "            return ''\n",
    "        result = ''\n",
    "        mapping = {}\n",
    "        for i in range(1,26):\n",
    "            t = (26*n-k)//(26-i)\n",
    "            result += chr(ord('a')+i-1) * t\n",
    "            n -= t \n",
    "            k -= t*i\n",
    "        result += n*'z'\n",
    "        return result \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        k -= n\n",
    "        num_z = int(k/25)\n",
    "        q = k%25\n",
    "        num_a = n-num_z-1 if(q!=0) else n-num_z\n",
    "        ans = (\"a\"*num_a)+chr(ord(\"a\")+q)+(\"z\"*num_z) if(q!=0) else (\"a\"*num_a)+(\"z\"*num_z)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        result = \"\"\n",
    "        start_n = ord('a')-1\n",
    "        for i in range(n):\n",
    "            if k-(n-1-i) - i*26 <= 26: #意味着最后是i个z，然后前面是aaaaa和最后一个数\n",
    "                break\n",
    "        for j in range(n-1-i):\n",
    "            result = result+\"a\"\n",
    "        result = result + chr(start_n+k-(n-1-i) - i*26)\n",
    "        for j in range(i):\n",
    "            result = result + \"z\"\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        ans = ''\n",
    "        for i in range(1, n+1):\n",
    "            cur = max(1, k-(n-i)*26)\n",
    "            ans += chr(96 + cur)\n",
    "            k -= cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        ans = ''\n",
    "        for i in range(1, n+1):\n",
    "            cur = max(1, k-(n-i)*26)\n",
    "            ans += chr(96 + cur)\n",
    "            k -= cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        s = []\n",
    "        for i in range(1, n + 1):\n",
    "            lower = max(1, k - (n - i) * 26)\n",
    "            k -= lower\n",
    "            s.append(ascii_lowercase[lower - 1])\n",
    "        return ''.join(s)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        ret_list = []\n",
    "        for i in range(1, n + 1):\n",
    "            curr_alpha_num = max(1, k - (n - i) * 26)\n",
    "            k -= curr_alpha_num\n",
    "            ret_list.append(ascii_lowercase[curr_alpha_num - 1])\n",
    "        return \"\".join(ret_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        s=[]\n",
    "        for i in range(1,n+1):\n",
    "            lower=max(1,k-(n-i)*26)\n",
    "            k-=lower\n",
    "            s.append(ascii_lowercase[lower-1])\n",
    "        return''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        ans = []\n",
    "        max_value = 26\n",
    "        for i in range(n):\n",
    "            value = max(1, k - (n - 1 - i) * 26)\n",
    "            k -= value\n",
    "            ans.append(ascii_lowercase[value - 1])\n",
    "        return ''.join(ans)\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        ans = []\n",
    "        for i in range(1, n + 1):\n",
    "            if (n-i)*26 >= k:\n",
    "                ans.append(ascii_lowercase[1-1])\n",
    "                k -= 1\n",
    "            else:\n",
    "                ans.append(ascii_lowercase[(k-(n-i)*26)-1])\n",
    "                k -= k-(n-i)*26\n",
    "        return (''.join(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        s = []\n",
    "        for i in range(1, n + 1):\n",
    "            lower = max(1, k - (n - i) * 26)\n",
    "            k -= lower\n",
    "            s.append(ascii_lowercase[lower - 1])\n",
    "        return ''.join(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        result = ['a' for _ in range(n)]\n",
    "        k -= n\n",
    "        p = n - 1\n",
    "        while True:\n",
    "            if k == 0:\n",
    "                break\n",
    "            elif k >= 25:\n",
    "                result[p] = 'z'\n",
    "                k -= 25\n",
    "                pass\n",
    "            else:\n",
    "                v = chr(k + ord('a'))\n",
    "                result[p] = v\n",
    "                break\n",
    "                pass\n",
    "            p -= 1\n",
    "            pass\n",
    "        return ''.join(result)\n",
    "        pass\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        ans = []\n",
    "        for i in range(1, n + 1):\n",
    "            l = max(1, k - (n - i) * 26)\n",
    "            k -= l\n",
    "            ans.append(ascii_lowercase[l-1])\n",
    "        return(''.join(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        ans = ['a'] * n\n",
    "        i, d = n - 1, k - n\n",
    "        while d > 25:\n",
    "            ans[i] = 'z'\n",
    "            d -= 25\n",
    "            i -= 1\n",
    "        ans[i] = chr(ord(ans[i]) + d)\n",
    "        return ''.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        lst = []\n",
    "        for i in range(1, n + 1):\n",
    "            lower = max(1, k - (n - i) * 26)\n",
    "            k -= lower\n",
    "            lst.append(chr(lower + 96))\n",
    "        return \"\".join(lst)\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "                a=list(\"a\"  for _ in range(n))\n",
    "                x=k-n\n",
    "                while x!=0:\n",
    "                    if x>=25:\n",
    "                        a[n-1]='z'\n",
    "                        n-=1\n",
    "                        x-=25\n",
    "                    else:\n",
    "                        a[n-1]= chr(ord(a[n-1])+x)\n",
    "                        break\n",
    "                return ''.join(a)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        tmp = [1 for i in range(n)]\n",
    "        p = n - 1\n",
    "        tool = k - n\n",
    "        while tool > 0:\n",
    "            nums = min(tool, 25)\n",
    "            tmp[p] += nums\n",
    "            tool -= nums\n",
    "            p -= 1\n",
    "        for i in range(len(tmp)):\n",
    "            tool = ord('a') + tmp[i] - 1\n",
    "            tmp[i] = chr(tool)\n",
    "        return \"\".join(tmp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        ans = ['a'] * n\n",
    "        i, d = n - 1, k - n\n",
    "        while d > 25:\n",
    "            ans[i] = 'z'\n",
    "            d -= 25\n",
    "            i -= 1\n",
    "        ans[i] = chr(ord(ans[i]) + d)\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        ans = ['a'] * n\n",
    "        i, d = n - 1, k - n\n",
    "        while d > 25:\n",
    "            ans[i] = 'z'\n",
    "            d -= 25\n",
    "            i -= 1\n",
    "        ans[i] = chr(ord(ans[i]) + d)\n",
    "        return ''.join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        s = []\n",
    "        for i in range(1, n + 1):\n",
    "            lower = max(1, k - (n - i) * 26)\n",
    "            k -= lower\n",
    "            s.append(ascii_lowercase[lower - 1])\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        ans = ['a'] * n\n",
    "        i, d = n - 1, k - n\n",
    "        while d > 25:\n",
    "            ans[i] = 'z'\n",
    "            d -= 25\n",
    "            i -= 1\n",
    "        ans[i] = chr(ord(ans[i]) + d)\n",
    "        return ''.join(ans)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "      ans = [\"a\"] * n\n",
    "      k -= n\n",
    "      i = n-1\n",
    "      while i > n-1-k//25:\n",
    "        ans[i] = \"z\"\n",
    "        i -= 1\n",
    "      k %= 25\n",
    "      if k: ans[i] = chr(ord(ans[i]) + k)\n",
    "      return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        # 初始化一个全为 'a' 的字符串，并减去所需的数值\n",
    "        result = ['a'] * n\n",
    "        k -= n\n",
    "        \n",
    "        index = n - 1\n",
    "        while k > 0:\n",
    "            # 添加到当前位置上的数值\n",
    "            add = min(k, 25) # 25是因为z比a大25\n",
    "            result[index] = chr(ord(result[index]) + add)\n",
    "            \n",
    "            k -= add\n",
    "            index -= 1\n",
    "            \n",
    "        return ''.join(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        ans: List[str]= ['\\0'] * n\n",
    "        # 从最后一个字符开始遍历\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            # 1. 由于前面还有 i 个位置需要填充，\n",
    "            #    所以当前位 digit 最大只能取到 k - i\n",
    "            # 2. 同时由于一个字符最大的数值是 26 ，\n",
    "            #    所以当前位 digit 最大只能取到 26\n",
    "            # 综上，当前位取 min(k - i, 26)\n",
    "            digit: int = min(k - i, 26)\n",
    "            # 从 k 分走 digit ，表示已使用\n",
    "            k -= digit\n",
    "            # 那么结果字符串中第 i 位的字符就是 digit + 'a' - 1\n",
    "            ans[i] = string.ascii_lowercase[digit - 1]\n",
    "\n",
    "        # 最后将所有的字符收集成一个字符串并返回\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        leftnode=n-1\n",
    "        leftval=k-n\n",
    "        strs = ['a']*n\n",
    "        while leftval>25:\n",
    "            strs[leftnode]='z'\n",
    "            leftval-=25\n",
    "            leftnode-=1\n",
    "        strs[leftnode]=chr(ord(strs[leftnode])+leftval)\n",
    "        return ''.join(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\r\n",
    "        ans = ['a'] * n\r\n",
    "        k -= n\r\n",
    "        i = n - 1\r\n",
    "        while k > 0:\r\n",
    "            ans[i] = chr(ord(ans[i]) + min(k, 25))\r\n",
    "            k -= min(k, 25)\r\n",
    "            i -= 1\r\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        ans = [\"a\"] * n\n",
    "        i, d = n - 1, k - n\n",
    "        while d > 25:\n",
    "            ans[i] = \"z\"\n",
    "            d -= 25\n",
    "            i -= 1\n",
    "        ans[i] = chr(ord(ans[i]) + d)\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        ret = []\n",
    "        while (n - 1) * 26 >= k - 1:\n",
    "            n -= 1\n",
    "            k -= 1\n",
    "            ret.append('a')\n",
    "        if k % 26 != 0: ret.append(chr(ord('a') - 1 + k % 26))\n",
    "        while k >= 26:\n",
    "            k -= 26\n",
    "            ret.append('z')\n",
    "        return ''.join(ret[:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        # 1 + 1 + 1 + 1(max 26)\n",
    "        temp = [1]*n\n",
    "        rest = k - n\n",
    "        p = -1\n",
    "        while rest > 25:\n",
    "            rest -= 25\n",
    "            temp[p] = 26\n",
    "            p -= 1\n",
    "        temp[p]+= rest\n",
    "        oo = ord(\"a\")-1\n",
    "        ans = ''\n",
    "        for x in temp:\n",
    "            ans += chr(oo+x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        \n",
    "        ans = [1]*n\n",
    "        k -= n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            x = 25 if 25 < k else k\n",
    "            ans[i] += x\n",
    "            k -= x\n",
    "        return \"\".join(chr(x+ord(\"a\")-1) for x in ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmallestString(self, n: int, k: int) -> str:\n",
    "        kd = k - n\n",
    "        ret_ints = [1 for _ in range(0, n)]\n",
    "        for i in range(0, len(ret_ints)):\n",
    "            if kd > 25:\n",
    "                ret_ints[i] = ret_ints[i]+25\n",
    "                kd = kd-25\n",
    "            else:\n",
    "                ret_ints[i] = ret_ints[i] + kd\n",
    "                break\n",
    "            \n",
    "        ret_ints.reverse()\n",
    "        ret_chrs = [chr(integer+96) for integer in ret_ints]\n",
    "\n",
    "        ret = \"\"\n",
    "        for s in ret_chrs:\n",
    "            s = str(s)\n",
    "            ret += s\n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
